\section{Desarrollo}
\noindent
Como comentamos en la introducción, necesitamos obtener una matriz $A$, que se obtiene del siguiente cálculo $A = M^{-1}*K$. Por lo tanto, necesitamos crear la matriz $M$ y la matriz $K$. Estas las generamos a partir de los datos de entrada. 

La matriz $M$, es una matriz que en su diagonal tiene los valores de la masa de cada piso (ver \textit{Enunciado}). Es decir $M_{i,i} = m_i$ donde $m_i$ es la masa del piso $i$. La masa de cada piso se obtiene sumando la masa propia del piso y la suma de las masas de los autos que están ubicados en ese piso. Es decir $m_i = m_0 + l_i * m_l + p_i * m_p$, donde:

\begin{itemize}
\item{$m_0$ es la masa por defecto del piso $i$.}
\item{$l_i$ es la cantidad de autos livianos en el piso $i$.}
\item{$p_i$ es la cantidad de autos pesados en el piso $i$.}
\item{$m_l$ es la masa de un auto liviano.}
\item{$m_p$ es la masa de un auto pesado.}
\end{itemize}

Una vez calculada la matriz $M$ necesitamos invertirla y as\'i obtenemos $M^{-1}$. 

Luego, a partir de los valores de coeficiente de rigidez calculamos la matriz tridiagonal $K$ (ver \textit{Enunciado}).
Las diagonales se escriben de la siguiente manera:

\begin{itemize}
\item{$K_{i,i} = - k_i - k_{i+1}$}
\item{$K_{i,i+1} = k_{i+1}$}
\item{$K_{i,i-1} = k_{i}$}
\end{itemize}

Donde:

\begin{itemize}
\item{$k_i$ es el coeficiente del piso actual $i$.}
%\item{$k_{i+1}$ es el coeficiente del piso superior al actual.}
%\item{$k_{i-1}$ es el coeficiente del piso inferior al actual.}
\end{itemize}

Una vez obtenidas ambas matrices, realizamos el producto y obtenemos la matriz $A$ que necesitabamos obtener. Ahora, el siguiente paso va a ser obtener la factorización QR de la matriz $A$.

\subsection{Factorización QR}
\noindent
La factorización de una matriz consiste en la descomposición de la matriz en dos matrices que multiplicadas obtenga la misma matriz. Es decir $A = Q * R$. Donde $Q$ es una matriz ortogonal y $R$ es una matriz triangular superior. Para calcular la factorización QR utilizamos los dos métodos vistos en clase: Givens y Householder.
\\

\subsubsection{Método de Givens}

El método de Givens consiste en realizar una serie de rotaciones de Givens las cuales van dejando en $0$ uno de los elementos debajo de la diagonal de la matriz $A$. En nuestro algoritmo al finalizar todas las rotaciones en la matriz A me va a quedar la matriz $R$, que es la matriz triangular superior. Y en otra matriz $W$, voy a ir guardando la productoria de las matrices por las cuales tuve que multiplicar la matriz $A$ para obtener un $0$ debajo de su diagonal. Para implementar Givens utilizamos el siguiente código:

\begin{verbatim}
for(int j = 1; j <= A.size(); j++){
  for(int i = j + 1; i <= A.size(); i++){
    if(fabs(A.get(i,j)) < 0.0000001){
      Matriz G = calcularMatrizG(A, i, j);
      mostrarMatriz(G);
      A = G.multiplicar(A);
      W = G.multiplicar(W);
    }
  }
}
Q = W.trasponer();
return Q;
\end{verbatim}

Como podemos ver en el código, lo que vamos haciendo es ir recorriendo el triangulo inferior de $A$, que es la que queremos dejar en $0$, y para cada valor que no sea cero calculamos la matriz $G$ de la siguiente manera:

\begin{verbatim}
Matriz G(A.size(), A.size());
vector<float> x;
x.push_back(A.get(col, col));
x.push_back(A.get(fil, col));
float norma2X = norma2(x);
for(int i = 1; i <= A.size(); i++){
  for(int j = 1; j <= A.size(); j++){
    if(i == fil){
      if(j == fil){   // Arriba a la izquierda
        G.set(i, j, x[0]/norma2X);
      }else{
        if(j == col){   // Arriba a la derecha
          G.set(i, j, (-1) * x[1]/norma2X);
        }
      }
    }else{
      if(i == col){
        if(j == fil){   // Abajo a la izquierda
          G.set(i, j,  x[1]/norma2X);
        }else{
          if(j == col){   // Abajo a la derecha
            G.set(i, j, x[0]/norma2X);
          }
        }
      }else{   // La identidad
        if(i == j){
          G.set(i, j, 1);
        }else{
          G.set(i,j, 0);
        }
      }
    }
  }
}
return G;
\end{verbatim}

Lo que primero hacemos es crearnos el vector $x = (x_1,x_2)$ correspondiente al valor que queremos poner en 0, llamemosle $a_{fc}$, $x_1$ será el valor que esta en la diagonal de la columna del $a_{fc}$, es decir el elemento $a_{cc}$. Luego $x_2 = a_{fc}$ quedando $x = (a_{cc},a_{fc})$ A partir de este valor crearemos la matriz G que tendrá la siguiente forma: para casi todos los $g_{ij}$ tendrá los valores de la identidad (es decir $1$ si $i=j$ y $0$ si $i\neq j$) pero para los valores correspondientes a las posiciones $(f, f)$, $(f, c)$, $(c, f)$ y $(f, f)$, le corresponde $\lvert x_1 \rvert / \lVert x \rVert$, $-\lvert x_2 \rvert / \lVert x \rVert$, $\lvert x_2 \rvert / \lVert x \rVert$ y $\lvert x_1 \rvert / \lVert x \rVert$ respectivamente. De esta manera nos queda definida la matriz $G$ que corresponde al vector $(a_{cc},a_{fc})$.
\\
Lo siguiente que haremos es multiplicar $G*A$ que nos dejará una $A_1$ con el valor $0$ en la posición $(f,c)$. De esta manera, al terminar nos queda $A_k = R$ y $Q^t = \prod_{i=1}^{k}G_k$, donde $k$ es la cantidad de ceros que había que poner en el triangulo inferior de $A$.
\\

\subsubsection{Método de Householder}

Otro método para calcular la factorización QR es el de Householder. Este método se basa en tomar reflexiones para que al multiplicar por una columna en $A$ nos queden en $0$ los valores del triángulo inferior de $A$ correspondiente a esa columna. En otras palabras lo que hacemos es reflejar la columna respecto a un hiper-plano de manera que el reflejo nos quede sobre uno de los ejes canónicos. El método de reflexiones lo implementamos de la siguiente manera:

\begin{verbatim}
Matriz Q(A.size(),A.size());
for(int k = 1; k <= A.size() - 1; k++){
  x = recuperarColumna(A, k);
  x[0] = x[0] - norma2(x);
  normaX = norma2(x);
  for(unsigned int i = 0; i < x.size(); i++){
    x[i] = x[i]/normaX;
  }
  Matriz W = calcularMatrizW(x, A.size());
  A = W.multiplicar(A);
  if(k == 1){
    Q = W;
  }else{
    Q = Q.multiplicar(W);
  }
}
return Q; 
\end{verbatim}
\newcommand{\R}{\ensuremath{\mathbb{R}}}

Como podemos ver para cada columna $j$ de la matriz $A$ tomamos el vector $v = (a_{jj},.., a_{nj})$ y creamos un vector $ x \in \R^{n-j}$ tal que $x = v - (|| x ||,0,..,0)$, dividimos a cada valor de $x$ por $|| x ||$ quedando en $x$ un vector unitario perpendicular al plano de reflexión elegido. Generamos $W$ que será una matriz asociada al plano antes mencionado. Esta matriz será: $W = I - 2*x*x^t$. Al finalizar el algoritmo retornaremos $Q = \prod_{k=1}^{n}W_k$ y en $A$ nos queda representada $R = \prod_{k=1}^{n}A_k$ donde $A_k = W*A_{k-1}$.

\subsection{Algoritmo QR}
\noindent
El algoritmo QR es un algoritmo iterativo, esto significa que realizará sucesivas veces la misma secuencia de pasos hasta que pare por algún criterio establecido. Por cada iteración el algoritmo calcula la factorización QR de $A$ y luego multiplica $R*Q$ lo que será nuestra nueva matriz $A$. Al terminar el algoritmo en la diagonal de $A$ tenemos una aproximación de los autovalores de la matriz $A$ original. En otras palabras, la iteración del algoritmo es: 

\begin{center}
 $A^{k+1} = R^k * Q^k$
\end{center}
Donde $A^k = Q^k * R^k$, es decir la factorización QR de $A^k$ es $Q^k * R^k$.
\\
El criterio de parada de este algoritmo es que la matriz este triangulada superiormente. Como la máquina no siempre ponia un 0 exacto, lo que hicimos fue redondear los números que eran muy próximos al 0, para que efectivamente este triangulada superiormente.

\subsection{Heurísticas}
\noindent
Para este trabajo también tuvimos que implementar heurísticas para reacomodar los autos de manera que al aparecer un inminente terremoto el edificio no se derrumbe. Para esto reacomodamos los autos con un criterio al azar de manera de cambiar la masa total de los pisos y modificando asi los autovalores que calculamos con los algoritmos anteriormente comentados.
\\
La primera heurística por la que optamos consiste en tomar un piso en base al primer índice de un vector (en el que tenemos las frecuencias naturales $(fn)$ del sistema) cuyo valor este entre 2.7 y 3.3. Una vez seleccionado el piso, sacamos 1 auto liviano y un auto pesado de ese piso, los movimos a un piso cuyo indice es la primera $fn$ que es menor a 2.7 o mayor a 3.3 y  volvemos a aplicar el algoritmo. Sin embargo, un inconveniente de este algoritmo es que puede pasar que mande los autos del piso $i$ al piso $j$ y que ahora sea el piso $j$ el piso no seguro y el algoritmo mande autos del piso $j$ al piso $i$ y así eternamente, por lo que no termina, es por eso que optamos por otro algoritmo, más allá de la simpleza de programar esta heurística.
\\
Otra heurística similar a la anterior es utilizar el mismo procedimiento pero en lugar de sacarle autos al piso elegido agregarselos, pero se presenta el mismo conflicto que la heurística anterior.
\\
También probamos con heurísticas que reacomodan de otra manera, en lugar de a dos autos por vez. En este otro procedimiento, lo que hacemos es buscar un piso, sacarle los autos livianos y colocarlos en otro piso con el mismo criterio de antes. Es una manera parecida a las anteriores, dado que en esta también muevo autos con la idea de cambiar la masa del piso y de esta manera se van a cambiar las frecuencias naturales del sistema que esta establecido.
\\
Luego de probar con estas heurísticas, probamos con una heurística que se fija en las $fn$. La idea de este tercer algoritmo heurístico es recorrer los pisos y ver la $fn$: si es menor que 3 le sacamos autos y si es mayor a 3 le agregamos autos.
\\
Como se puede ver en la última heurística lo unico que cambia es que si antes sacabamos autos, ahora agregamos y viceversa.
